package com.xigua._数学;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description:  f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 。
 *
 * 例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。
 * 给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。
 * @date 2022/8/2813:23
 */
public class _793_阶乘函数后K个零 {

    public static void main(String[] args) {
        preimageSizeFZF(4);
    }

    public static int preimageSizeFZF(int k) {
        long l = k - 1,r = k * 10L + 1;
        while(l + 1 < r){
            long m = l + r >> 1,t = f(m);
            if(t == k) return 5;
            else if(t < k) l = m;
            else r = m;
        }
        return 0;
    }

    static long f(long n){
        if(n == 0) return 0;
        return n / 5 + f(n / 5);
    }

}
